package com.yzh.homework;

/**
 * @author 于振晗
 * @title: BinarySearch
 * @description: TODO 二分查找
 * @date 2020年09月01日
 * @path com.yzh.homework
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10};

        int i = notRecursion(arr, 8);
        System.out.println(i);
        int recursion = Recursion(arr, 8, 0, arr.length - 1);
        System.out.println(recursion);
    }

    public static int notRecursion(int[] arr, int key) {
        int low = 0, high = arr.length - 1;
        while (!(low > high)) {
            int mid = (low + high) / 2;
            if (arr[mid] > key) {
                high = --mid;
            } else if (arr[mid] < key) {
                low = ++mid;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static int Recursion(int[] arr, int key, int low, int high) {
        int mid = (low + high) / 2;
        if (low > high) {
            return -1;
        }
        if (arr[mid] > key) {
            return Recursion(arr, key, low, --mid);
        } else if (arr[mid] < key) {
            return Recursion(arr, key, ++mid, high);
        } else {
            return mid;
        }
    }
}
